package com.south.base.test.arithmetic.arrays;

import org.junit.Assert;
import org.junit.Test;

import java.util.*;

/**
 * 重复数组处理
 *
 * @author Administrator
 * @date 2020/6/12 10:44
 */
public class DuplicatesArr {
    /**
     * 给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
     * 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
     */
    @Test
    public void removeDuplicates() {
        int[] a = new int[]{1, 1, 2};
        int res = removeDuplicates(a);
        Assert.assertEquals(2, res);
        Assert.assertArrayEquals(new int[]{1, 2, 2}, a);

        a = new int[]{0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
        res = removeDuplicates(a);
        Assert.assertEquals(5, res);
        Assert.assertArrayEquals(new int[]{0, 1, 2, 3, 4, 2, 2, 3, 3, 4}, a);
    }

    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return 1;
        }
        int res = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[res] != nums[i]) {
                res++;
                nums[res] = nums[i];
            }
        }
        return res + 1;
    }

    /**
     * 移除元素
     * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
     * 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
     * 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
     */
    @Test
    public void removeElement() {
        int[] a = new int[]{1, 1, 2};
        int res = removeElement(a, 1);
        Assert.assertEquals(1, res);
        Assert.assertArrayEquals(new int[]{2, 1, 2}, a);

        a = new int[]{3, 2, 2, 3};
        res = removeElement(a, 3);
        Assert.assertEquals(2, res);
        Assert.assertArrayEquals(new int[]{2, 2, 2, 3}, a);

        a = new int[]{0, 1, 2, 2, 3, 0, 4, 2};
        res = removeElement(a, 2);
        Assert.assertEquals(5, res);
        Assert.assertArrayEquals(new int[]{0, 1, 3, 0, 4, 0, 4, 2}, a);
    }

    public int removeElement(int[] nums, int val) {
        if (nums.length == 0) {
            return 0;
        }
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            if (val != nums[i]) {
                nums[res] = nums[i];
                res++;
            }
        }
        return res;
    }

    /**
     * 存在重复元素
     * 给定一个整数数组，判断是否存在重复元素。
     * 如果任意一值在数组中出现至少两次，函数返回 true 。
     * 如果数组中每个元素都不相同，则返回 false 。
     */
    @Test
    public void containsDuplicate() {
        Assert.assertTrue(containsDuplicate(new int[]{1, 2, 3, 1}));
        Assert.assertFalse(containsDuplicate(new int[]{1, 2, 3, 4}));
        Assert.assertTrue(containsDuplicate(new int[]{1, 1, 1, 3, 3, 4, 3, 2, 4, 2}));
    }

    public boolean containsDuplicate(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            Integer integer = map.get(num);
            if (integer == null) {
                map.put(num, 1);
            } else {
                return true;
            }
        }
        return false;
    }

    /**
     * 存在重复元素 II
     * 给定一个整数数组和一个整数 k，
     * 判断数组中是否存在两个不同的索引 i 和 j，
     * 使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。
     */
    @Test
    public void containsNearbyDuplicate() {
        Assert.assertFalse(containsNearbyDuplicate(new int[]{1, 2, 3, 1, 2, 3}, 2));
        Assert.assertTrue(containsNearbyDuplicate(new int[]{1, 0, 1, 1}, 1));
        Assert.assertTrue(containsNearbyDuplicate(new int[]{1, 2, 3, 1}, 3));
    }

    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            Integer index = map.get(num);
            if (index != null && i - index <= k) {
                return true;
            }
            map.put(num, i);
        }
        return false;
    }

    /**
     * 全排列 II
     * 给定一个可包含重复数字的序列，返回所有不重复的全排列。
     */
    @Test
    public void permuteUnique() {
        Assert.assertEquals("[[1, 1, 2], [1, 2, 1], [2, 1, 1]]", permuteUnique(new int[]{1, 1, 2}).toString());
    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }

        // 排序（升序或者降序都可以），排序是剪枝的前提
        Arrays.sort(nums);

        boolean[] used = new boolean[len];
        // 使用 Deque 是 Java 官方 Stack 类的建议
        Deque<Integer> path = new ArrayDeque<>(len);
        dfs(nums, used, path, res);
        return res;
    }

    private void dfs(int[] nums, boolean[] used, Deque<Integer> path, List<List<Integer>> res) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; ++i) {
            if (used[i]) {
                continue;
            }

            // 剪枝条件：i > 0 是为了保证 nums[i - 1] 有意义
            // 写 !used[i - 1] 是因为 nums[i - 1] 在深度优先遍历的过程中刚刚被撤销选择
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }

            path.addLast(nums[i]);
            used[i] = true;

            dfs(nums, used, path, res);
            // 回溯部分的代码，和 dfs 之前的代码是对称的
            used[i] = false;
            path.removeLast();
        }
    }
}
